# Dijkstra：在所有路径中搜索vi到vj的最小权重

import numpy as np
import pandas as pd
from tools.Conversion import Conversion
from tools.Input import Input
from tools.Output import Output


class Dijkstra:
    __name = 'Dijkstra'

    @staticmethod
    def do_dijkstra():
        # g = Input.input_graph_matrix()  # 输入有向图
        g = Conversion.graph_arr_2_matrix(Input.get_graph2(), direction=True)  # 获取一个图（例3.4.2）
        print('输入的图为：')
        Output.print_graph_matrix(g)

        v_set = g[0]  # 点集
        s_set = g[1]  # 边集

        while True:
            v0 = input('请输入起始点：')
            try:
                v0_index = v_set.index(v0)
                break
            except ValueError:
                print('输入错误')

        fixed = [v0_index]  # 固定下来的点

        print('生成过程：')
        for i in range(len(v_set) - 1):  # 对于每个点
            s_min = 0  # 权值最小点的下标，从第一个开始
            for s in s_set[v0_index]:  # 遍历起始点的边集
                if s_set[v0_index][s_min] > s and s_set[v0_index].index(s) not in fixed:  # 边的权值小于最小边且未固定
                    s_min = s_set[v0_index].index(s)
            if s_set[v0_index][s_min] == float('inf'):  # 未找到最小边，退出
                break
            fixed.append(s_min)  # 固定最小边的端点

            for s in s_set[s_min]:  # 遍历最小边端点的边
                index = s_set[s_min].index(s)
                if index not in fixed:  # 找到未固定的点
                    s_set[v0_index][index] = min(s_set[v0_index][index], s + s_set[v0_index][s_min])  # 起点更新权值

            print('更新：', v0, '到', v_set[s_min], '的最短路长：', s_set[v0_index][s_min])
            print(pd.DataFrame([s_set[v0_index]], index=[v0], columns=v_set))

        df = pd.DataFrame(s_set, index=v_set, columns=v_set)
        precursor = np.array(df.idxmin(axis=0))  # 前驱节点

        print('最短路长：')
        print(pd.DataFrame([s_set[v0_index]], index=[v0], columns=v_set))
        print('前驱节点：')
        print(pd.DataFrame([precursor], index=[v0], columns=v_set))
